0% completed
Problem Statement
Given a root of the binary tree, connect each node with its level order successor. The last node of each level should point to the first node of the next level.
Examples
Example 1
- Input: root = [1, 2, 3, 4, 5, 6, 7]
- Output: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> null
- Explanation: The tree is traversed level by level using BFS. Each node is connected to its next node in level order traversal, including connections between levels. The last node (
7) points tonull.
Example 2
- Input: root = [12, 7, 1, 9, null, 10, 5]
- Output: 12 -> 7 -> 1 -> 9 -> 10 -> 5 -> null
- Explanation: Each node is connected to its next node in level order traversal. The last node (
5) points tonull, completing the connection of all level order siblings.
Constraints:
- The number of nodes in the tree is in the range [0, 212 - 1].
-1000 <= Node.val <= 1000
Solution
In the previous problem, we connected nodes within the same level. Here, we extend the connection across levels, linking every node to its next node in level order traversal. Using BFS, we process nodes one by one, maintaining a previousNode to link the dequeued node. The last node in traversal points to null, forming a single linked list that follows the tree’s level order sequence.
Step-by-Step Algorithm
-
Handle the Base Case:
- If the tree is empty (
root == null), returnnull.
- If the tree is empty (
-
Initialize BFS Traversal:
- Create a queue and enqueue the root node to start the level order traversal.
- Define
previousNode = nullto track the last processed node and establish connections. - Define
currentNodeto hold the node dequeued at each step.
-
Process Nodes One by One:
- While the queue is not empty:
- Dequeue the front node and store it in
currentNode. - If
previousNodeis not null, connectpreviousNode.next = currentNodeto maintain level order linking. - Update
previousNode = currentNodeto track the last processed node.
- Dequeue the front node and store it in
- While the queue is not empty:
-
Enqueue the Children of the Current Node:
- If
currentNode.leftexists, enqueue it. - If
currentNode.rightexists, enqueue it.
- If
-
Continue Until All Nodes Are Processed.
- The last node in traversal will automatically point to
null, marking the end of the sequence.
- The last node in traversal will automatically point to
-
Return the Root Node After All Connections Are Established.
Algorithm Walkthrough
-
Initialize BFS Traversal:
- Start with the root node
12. - Initialize an empty queue and enqueue
12. - Initialize
previousNode = null.
Queue:
[12] - Start with the root node
-
Process Node 12:
- Dequeue
12:- Since
previousNodeisnull, assignpreviousNode = 12. - Enqueue left child
7. - Enqueue right child
1.
- Since
Queue after processing:
[7, 1]
Next Pointer Connection:12 -> null - Dequeue
-
Process Node 7:
- Dequeue
7:- Connect
12.next = 7(link12to7). - Update
previousNode = 7. - Enqueue left child
9(no right child).
- Connect
Queue after processing:
[1, 9]
Next Pointer Connections:12 -> 7 -> null - Dequeue
-
Process Node 1:
- Dequeue
1:- Connect
7.next = 1(link7to1). - Update
previousNode = 1. - Enqueue left child
10. - Enqueue right child
5.
- Connect
Queue after processing:
[9, 10, 5]
Next Pointer Connections:12 -> 7 -> 1 -> null - Dequeue
-
Process Node 9:
- Dequeue
9:- Connect
1.next = 9(link1to9). - Update
previousNode = 9. 9has no children.
- Connect
Queue after processing:
[10, 5]
Next Pointer Connections:12 -> 7 -> 1 -> 9 -> null - Dequeue
-
Process Node 10:
- Dequeue
10:- Connect
9.next = 10(link9to10). - Update
previousNode = 10. 10has no children.
- Connect
Queue after processing:
[5]
Next Pointer Connections:12 -> 7 -> 1 -> 9 -> 10 -> null - Dequeue
-
Process Node 5:
- Dequeue
5:- Connect
10.next = 5(link10to5). - Update
previousNode = 5. 5has no children.
- Connect
Queue after processing:
[]
Next Pointer Connections:12 -> 7 -> 1 -> 9 -> 10 -> 5 -> null - Dequeue
Final Connected Tree Representation
12 -> 7 -> 1 -> 9 -> 10 -> 5 -> null
Code
Here is the code for this algorithm:
Complexity Analysis
Time Complexity
The time complexity of the above algorithm is
Space Complexity
The space complexity of the above algorithm will be
On this page
Problem Statement
Examples
Solution
Step-by-Step Algorithm
Algorithm Walkthrough
Code
Complexity Analysis
Time Complexity
Space Complexity